package leetcode;

//判断一棵树是否是平衡二叉树
//Definition for a binary tree node.
  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {

    // public int getHeight(TreeNode root) {
    // if(root == null){
    //     return 0;
    // }
    // int leftHeight = getHeight(root.left);
    // int rightHeight = getHeight(root.right);
    // return Math.max(leftHeight,rightHeight) + 1;
    // }

    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if(leftHeight < 0) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight-rightHeight)<= 1) {
            return Math.max(leftHeight,rightHeight) + 1;
        }else {
            return -1;
        }
    }

    public boolean isBalanced(TreeNode root) {
        //解法1
        // if(root == null) {
        //     return true;
        // }
        // int leftH = getHeight(root.left);
        // int rightH = getHeight(root.right);
        // if(Math.abs(leftH-rightH)< 2 && isBalanced(root.left) && isBalanced(root.right)) {
        //     return true;
        // }
        // return false;

        //解法2
        if(root == null) {
            return true;
        }
        return getHeight(root) >= 0;
    }
}